#include <dbg.h>
#include <gtest/gtest.h>

using std::vector;

class Solution {
public:
    static void nextPermutation(vector<int>& nums) {
        int i = static_cast<int>(nums.size()) - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {  // 从后往前找到第一个升序对
            --i;  // 满足i的右边有大于i的数，右侧单调递减
        }
        dbg(i);

        if (i >= 0) {
            int j = static_cast<int>(nums.size()) - 1;
            while (j >= 0 &&
                   nums[i] >= nums[j]) {  // 从后往前找到第一个大于nums[i]的数
                --j;
            }
            dbg(j);
            std::swap(nums[i], nums[j]);  // 交换后，i右边的数仍然是单调递减的
            dbg(nums);
        }
        std::reverse(nums.begin() + i + 1,
                     nums.end());  // 反转i右边的数，使其变为单调递增
        dbg(nums);
    }
};

TEST(TEST1, nextPermutation) {
    vector nums{1, 2, 3};
    const vector res{1, 3, 2};

    Solution::nextPermutation(nums);
    EXPECT_EQ(nums, res);
}

TEST(TEST2, nextPermutation) {
    vector nums{1, 2, 3, 5, 4};
    const vector res{1, 2, 4, 3, 5};

    Solution::nextPermutation(nums);
    EXPECT_EQ(nums, res);
}

int main(int argc, char** argv) {
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}